package niuke;

import niuke.common.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * @题目
 * NC45 实现二叉树先序，中序和后序遍历
 *
 * @描述
 * 给定一棵二叉树，分别按照二叉树先序，中序和后序打印所有的节点。
 * 数据范围：10000≤n≤1000，树上每个节点的val值满足 1000≤val≤100
 *
 * @要求：
 * 空间复杂度 O(n)O(n)，时间复杂度 O(n)O(n)
 * @样例解释
 *      1
 *     / \
 *   2    3
 * 如图二叉树结构
 *
 * @示例1
 * 输入：
 * {1,2,3}
 * 复制
 * 返回值：
 * [[1,2,3],[2,1,3],[2,3,1]]
 *
 * 说明：
 * 如题面图
 *
 * @示例2
 * 输入：
 * {}
 * 复制
 * 返回值：
 * [[],[],[]]
 * 复制
 * 备注：
 * 10^6n≤10 的6次方
 * */
public class TraverseBianyTree {
    public static void main(String[] args) {
        TraverseBianyTree bianyTree = new TraverseBianyTree();
        TreeNode root = new TreeNode();
//        root.val=1;
//        TreeNode node2 = new TreeNode();
//        node2.val = 2;
//        TreeNode node3 = new TreeNode();
//        node3.val = 3;
//        root.left = node2;
//        root.right = node3;
        int[][] pre = bianyTree.threeOrders(null);
        System.out.println(pre);
    }
    /**
     *
     * @param root TreeNode类 the root of binary tree
     * @return int整型二维数组
     */
    public int[][] threeOrders (TreeNode root) {

        // write code here
        int[][] result = new int[3][];
        if (root == null){
            result[0] = new int[0];
            result[1] = new int[0];
            result[2] = new int[0];
            return result;
        }
        //前序遍历
        List<Integer> pre = new ArrayList<>();
        preOrderTraverse(root,pre);
        result[0] = new int[pre.size()];
        for (int i = 0; i < pre.size(); i++) {
            result[0][i] = pre.get(i);
        }

        // 中序遍历
        List<Integer> middle = new ArrayList<>();
        middleOrderTraverse(root,middle);
        result[1] = new int[middle.size()];
        for (int i = 0; i < middle.size(); i++) {
            result[1][i] = middle.get(i);
        }

        //后序遍历
        List<Integer> after = new ArrayList<>();
        afterOrderTraverse(root,after);
        result[2] = new int[after.size()];
        for (int i = 0; i < after.size(); i++) {
            result[2][i] = after.get(i);
        }

        return result;
    }

    /**
     * 前序遍历
     * @param root
     * @param preResult
     * @return List<Integer>
     * */
    public List<Integer> preOrderTraverse(TreeNode root, List<Integer> preResult){
        if (root == null){
            return preResult;
        }
        preResult.add(root.val);
        preOrderTraverse(root.left,preResult);
        preOrderTraverse(root.right,preResult);
        return preResult;
    }

    /**
     * 中序遍历
     * @param root
     * @param preResult
     * @return List<Integer>
     * */
    public List<Integer> middleOrderTraverse(TreeNode root, List<Integer> preResult){
        if (root == null){
            return preResult;
        }
        middleOrderTraverse(root.left,preResult);
        preResult.add(root.val);
        middleOrderTraverse(root.right,preResult);
        return preResult;
    }

    /**
     * 后序遍历
     * @param root
     * @param preResult
     * @return List<Integer>
     * */
    public List<Integer> afterOrderTraverse(TreeNode root, List<Integer> preResult){
        if (root == null){
            return preResult;
        }
        afterOrderTraverse(root.left,preResult);
        afterOrderTraverse(root.right,preResult);
        preResult.add(root.val);
        return preResult;
    }


}
